package org.example.top40;

public class main26 {
    //重排列表
    //输入：head = [1,2,3,4,5]
    //输出：[1,5,2,4,3]
    //思路：快慢指针中间节点fast.next!=null开始，保证能获得中间节点的前一个
    //反转右边的链表
    //合并两个链表，交替插入，条件只看right因为它始终最短
    public static void main(String[] args) {
        ListNode head = builder();
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode right = slow.next;
        ListNode left = head;
        slow.next = null;
        right = reverseListNode(right);
        head = merege(left, right);
        System.out.println(head.next.val+"->"+head.next.next.val);
    }

    private static ListNode merege(ListNode left, ListNode right) {
        ListNode dummy = new ListNode(-1);
        ListNode pre = dummy;
        while (right != null) {
            pre.next = left;
            left = left.next;
            pre = pre.next;
            pre.next=right;
            right=right.next;
            pre=pre.next;
        }
        if(left!=null){
            pre.next=left;
        }
        return dummy.next;
    }

    private static ListNode reverseListNode(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        ListNode next = null;
        while (cur != null) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;

    }

    private static ListNode builder() {
        ListNode head = new ListNode(1);
        ListNode node1 = new ListNode(2);
        ListNode node2 = new ListNode(3);
        ListNode node3 = new ListNode(4);
        ListNode node4 = new ListNode(5);
        head.next = node1;
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        return head;
    }
}
